package com.liang.leetcode.binarytree.exercise;

import com.liang.leetcode.binarytree.entity.TreeNode;
import com.liang.leetcode.binarytree.util.BiTreeUtil;

import java.util.HashMap;
import java.util.Map;

/**
 * 106.从中序与后序遍历序列构造二叉树
 * 给定两个整数数组 inorder 和 postorder，其中 inorder 是二叉树的中序遍历，postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树
 * 注意：inorder 和 postorder 都由不同的值组成
 */
public class BiTree17_BuildTree {
    public static void main(String[] args) {
        // 根据中序遍历和后序遍历构造二叉树
        TreeNode treeNode = buildTree();
        // 先序遍历打印这棵二叉树
        System.out.println("先序遍历：" + BiTreeUtil.preorderTraversal(treeNode));
    }

    // 存储中序节点数值对应的索引，方便根据数值查找位置
    static Map<Integer, Integer> inorderMap;

    public static TreeNode buildTree() {
        // 前序遍历
        int[] preorder = {3, 9, 20, 15, 7};
        // 中序遍历：根据前序或后序遍历序列中根节点在中序遍历序列的位置，分割左右子树
        int[] inorder = {9, 3, 15, 20, 7};
        // 后序遍历
        int[] postorder = {9, 15, 7, 20, 3};
        inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        // 中序 + 后序
        return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
        // 中序 + 前序
        // return build2(inorder, 0, inorder.length - 1, preorder, 0, preorder.length - 1);
    }

    /**
     * 根据中序遍历和后序遍历的数组重建二叉树
     * @param inorder 中序遍历数组
     * @param inStart 中序遍历数组起始位置
     * @param inEnd 中序遍历数组结束位置（不含）
     * @param postorder 后序遍历数组
     * @param postStart 后序遍历数组起始位置
     * @param postEnd 后序遍历数组结束位置（不含）
     * @return 重建的二叉树的根节点
     */
    public static TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        // 中序遍历序列、后序遍历序列的边界判断
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }
        // 找到根节点（后序遍历的最后一个元素）在中序遍历中的位置
        int rootIndex = inorderMap.get(postorder[postEnd]);
        // 构造根结点
        TreeNode root = new TreeNode(inorder[rootIndex]);
        // 根据中序遍历序列根节点位置，计算左子树节点个数，再确定后序遍历序列左子树结束位置
        // int postIndex = postStart + (rootIndex - inStart);
        // // 递归构造左子树
        // root.left = build(inorder, inStart, inStart + rootIndex,
        //         postorder, postStart, postIndex - 1);
        // // 递归构造右子树
        // root.right = build(inorder, rootIndex + 1, inEnd,
        //         postorder, postIndex, postEnd - 1);

        // 计算左子树的节点个数，再确定左右子树边界值
        int leftTreeSize = rootIndex - inStart;
        root.left = build(inorder, inStart, rootIndex - 1, // inEnd: inStart + rootIndex
                postorder, postStart, postStart + leftTreeSize - 1);
        root.right = build(inorder, rootIndex + 1, inEnd,
                postorder, postStart + leftTreeSize, postEnd - 1);

        return root;
    }

    /**
     * 相关题目
     * 105.从前序与中序遍历序列构造二叉树
     */
    public static TreeNode build2(int[] inorder, int inStart, int inEnd, int[] preorder, int preStart, int preEnd) {
        // 中序遍历序列、先序遍历序列的边界判断
        if (inStart > inEnd || preStart > preEnd) {
            return null;
        }

        // 找到根节点（前序遍历的第一个元素）在中序遍历中的位置
        int rootIndex = inorderMap.get(preorder[preStart]);
        // 构造根结点，使用先序遍历的第一个元素作为根节点的值
        TreeNode root = new TreeNode(inorder[rootIndex]); // new TreeNode(preorder[preStart]);

        // 根据中序遍历序列根节点位置，计算左子树节点个数，再确定前序遍历序列左子树结束位置
        // int preIndex = preStart + (rootIndex - inStart);
        // // 递归构造左子树
        // root.left = build2(inorder, inStart, rootIndex - 1,
        //         preorder, preStart + 1, preIndex);
        // // 递归构造右子树
        // root.right = build2(inorder, rootIndex + 1, inEnd,
        //         preorder, preIndex + 1, preEnd);

        // 计算左子树的节点个数，再确定左右子树边界值
        int leftTreeSize = rootIndex - inStart;
        root.left = build2(inorder, inStart, rootIndex - 1,// 排除已经构造过的节点
                preorder, preStart + 1, preStart + leftTreeSize);
        root.right = build2(inorder, rootIndex + 1, inEnd,
                preorder, preStart + leftTreeSize + 1, preEnd);

        return root;
    }

}
